/*
https://leetcode.cn/problems/shopping-offers/description/
638. 大礼包
*/

class Solution {
public:
    unordered_map<string, int> mp;
    string vecToStr(vector<int> &needs){
        string str = "";
        for(int i = 0 ; i < needs.size(); i++){
            str += to_string(needs[i]) + ',';
        }
        return str;
    }
    int dfs(vector<int> &needs, vector<vector<int>> &special, vector<int>& price){
        int n = needs.size();
        int m = special.size();
        int min_cost = 0;
        string key = vecToStr(needs);
        if(mp.count(key)) return mp[key];
        for(int i = 0; i < n; i++)
            min_cost += price[i] * needs[i];
        for(int i = 0; i < m; i++){ //用第i个大礼包
            bool flag = true;
            for(int j = 0; j < n; j++){
                if(special[i][j] > needs[j]){
                    flag = false;
                    break;
                }
            }

            if(flag) //可以用第i个大礼包
            {
                for(int j = 0; j < n; j++){
                    needs[j] -= special[i][j];
                }
                min_cost = min(min_cost, special[i][n] + dfs(needs, special, price));
                for(int j = 0; j < n; j++){
                    needs[j] += special[i][j];
                } 
            }
        }
        mp[key] = min_cost;
        return min_cost;
    }

    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        return dfs(needs, special, price);
    }
};
